{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Common Region"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSmallestRegion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小公共区域"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一些区域列表&nbsp;<code>regions</code> ，每个列表的第一个区域都包含这个列表内所有其他区域。</p>\n",
    "\n",
    "<p>很自然地，如果区域&nbsp;<code>X</code> 包含区域&nbsp;<code>Y</code> ，那么区域&nbsp;<code>X</code> &nbsp;比区域&nbsp;<code>Y</code> 大。</p>\n",
    "\n",
    "<p>给定两个区域&nbsp;<code>region1</code>&nbsp;和&nbsp;<code>region2</code> ，找到同时包含这两个区域的&nbsp;<strong>最小&nbsp;</strong>区域。</p>\n",
    "\n",
    "<p>如果区域列表中&nbsp;<code>r1</code>&nbsp;包含&nbsp;<code>r2</code>&nbsp;和&nbsp;<code>r3</code> ，那么数据保证&nbsp;<code>r2</code> 不会包含&nbsp;<code>r3</code>&nbsp;。</p>\n",
    "\n",
    "<p>数据同样保证最小公共区域一定存在。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：\n",
    "</strong>regions = [[&quot;Earth&quot;,&quot;North America&quot;,&quot;South America&quot;],\n",
    "[&quot;North America&quot;,&quot;United States&quot;,&quot;Canada&quot;],\n",
    "[&quot;United States&quot;,&quot;New York&quot;,&quot;Boston&quot;],\n",
    "[&quot;Canada&quot;,&quot;Ontario&quot;,&quot;Quebec&quot;],\n",
    "[&quot;South America&quot;,&quot;Brazil&quot;]],\n",
    "region1 = &quot;Quebec&quot;,\n",
    "region2 = &quot;New York&quot;\n",
    "<strong>输出：</strong>&quot;North America&quot;\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= regions.length &lt;= 10^4</code></li>\n",
    "\t<li><code>region1 != region2</code></li>\n",
    "\t<li>所有字符串只包含英文字母和空格，且最多只有&nbsp;20 个字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-common-region](https://leetcode.cn/problems/smallest-common-region/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-common-region](https://leetcode.cn/problems/smallest-common-region/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"Earth\",\"North America\",\"South America\"],[\"North America\",\"United States\",\"Canada\"],[\"United States\",\"New York\",\"Boston\"],[\"Canada\",\"Ontario\",\"Quebec\"],[\"South America\",\"Brazil\"]]\\n\"Quebec\"\\n\"New York\"', '[[\"Earth\", \"North America\", \"South America\"],[\"North America\", \"United States\", \"Canada\"],[\"United States\", \"New York\", \"Boston\"],[\"Canada\", \"Ontario\", \"Quebec\"],[\"South America\", \"Brazil\"]]\\n\"Canada\"\\n\"South America\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        for i in regions[::-1]:\n",
    "            for j in i:\n",
    "                if j==region1:region1=i[0]\n",
    "                if j==region2:region2=i[0]\n",
    "                if region2==region1:return region1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        dad = {}\n",
    "        for region in regions:\n",
    "            for a in region[1:]:\n",
    "                dad[a] = region[0]\n",
    "        \n",
    "        dad1 = [region1]\n",
    "        a = region1\n",
    "        while a in dad:\n",
    "            a = dad[a]\n",
    "            dad1.append(a)\n",
    "        \n",
    "        dad2 = [region2]\n",
    "        a = region2\n",
    "        while a in dad:\n",
    "            a = dad[a]\n",
    "            dad2.append(a)\n",
    "        \n",
    "        dad1 = dad1[::-1]\n",
    "        dad2 = dad2[::-1]\n",
    "        ans = []\n",
    "        for a, b in zip(dad1, dad2):\n",
    "            if a== b:\n",
    "                ans.append(a)\n",
    "        return ans[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        placeDict = collections.defaultdict(str)\n",
    "        for region in regions:\n",
    "            for i in region[1:]:\n",
    "                placeDict[i] = region[0]\n",
    "        \n",
    "        stack1, stack2 = [region1], [region2]\n",
    "        while placeDict[stack1[-1]]:    stack1.append(placeDict[stack1[-1]])\n",
    "        while placeDict[stack2[-1]]:    stack2.append(placeDict[stack2[-1]])\n",
    "        while True:\n",
    "            cur = stack1.pop()\n",
    "            stack2.pop()\n",
    "            if not stack1 or not stack2 or stack1[-1] != stack2[-1]:\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        mapping = dict()\n",
    "        for region in regions:\n",
    "            for i, it in enumerate(region):\n",
    "                if i == 0:\n",
    "                    root = it\n",
    "                else:\n",
    "                    if it not in mapping:\n",
    "                        mapping[it] = root\n",
    "\n",
    "        def find_path(region):\n",
    "            result = list()\n",
    "            while region in mapping:\n",
    "                result.append(region)\n",
    "                region = mapping[region]\n",
    "            result.append(region)\n",
    "            return result\n",
    "\n",
    "        path1 = find_path(region1)\n",
    "        path2 = find_path(region2)\n",
    "        # print(path1, path2)\n",
    "        i, j = len(path1) - 1, len(path2) - 1\n",
    "        result = None\n",
    "        while path1[i] == path2[j]:\n",
    "            result = path1[i]\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        fa=dict()\n",
    "        for ls in regions:\n",
    "            for i in range(1,len(ls)):\n",
    "                fa[ls[i]]=ls[0]\n",
    "        s1,s2=set(),set()\n",
    "        while region1!=region2:\n",
    "            if region1 in fa:\n",
    "                s1.add(region1)\n",
    "                if region1 in s2:\n",
    "                    return region1\n",
    "                region1=fa[region1]\n",
    "            if region2 in fa:\n",
    "                s2.add(region2)\n",
    "                if region2 in s1:\n",
    "                    return region2\n",
    "                region2=fa[region2]\n",
    "        print(s1,s2,region1,region2)\n",
    "        return region1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        placeDict = collections.defaultdict(str)\n",
    "        for region in regions:\n",
    "            for i in region[1:]:\n",
    "                placeDict[i] = region[0]\n",
    "        \n",
    "        stack1, stack2 = [region1], [region2]\n",
    "        while placeDict[stack1[-1]]:    stack1.append(placeDict[stack1[-1]])\n",
    "        while placeDict[stack2[-1]]:    stack2.append(placeDict[stack2[-1]])\n",
    "        while True:\n",
    "            cur = stack1.pop()\n",
    "            stack2.pop()\n",
    "            if not stack1 or not stack2 or stack1[-1] != stack2[-1]:\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        parent = {}\n",
    "        for region in regions:\n",
    "            for i in range(1, len(region)):\n",
    "                parent[region[i]] = region[0]\n",
    "        parents1 = set()\n",
    "        cur = region1\n",
    "        while cur in parent.keys():\n",
    "            parents1.add(cur)\n",
    "            cur = parent[cur]\n",
    "        cur = region2\n",
    "        while cur in parent.keys():\n",
    "            if cur in parents1:\n",
    "                return cur\n",
    "            cur = parent[cur]\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        # 多叉树的最近公共祖先\n",
    "        # 用哈希表储存每一个region的父区域\n",
    "        parents = dict()\n",
    "        for region in regions:\n",
    "            for i in range(1, len(region)):\n",
    "                parents[region[i]] = region[0]\n",
    "        # 先找到regions1自底向上的全部父区域，存在parents1哈希集合中\n",
    "        parents1 = {region1}\n",
    "        while(region1 in parents):\n",
    "            parents1.add(parents[region1])\n",
    "            region1 = parents[region1]\n",
    "        # 寻找regions2自底向上的每一个父区域，判断其是否位于parents1中\n",
    "        while(region2 not in parents1):\n",
    "            region2 = parents[region2]\n",
    "        return region2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        # 多叉树的最近公共祖先\n",
    "        # 用哈希表储存每一个region的父区域\n",
    "        parents = dict()\n",
    "        for region in regions:\n",
    "            for i in range(1, len(region)):\n",
    "                parents[region[i]] = region[0]\n",
    "        # 先找到regions1自底向上的全部父区域，存在parents1哈希集合中\n",
    "        parents1 = {region1}\n",
    "        while(region1 in parents):\n",
    "            parents1.add(parents[region1])\n",
    "            region1 = parents[region1]\n",
    "        # 寻找regions2自底向上的每一个父区域，判断其是否位于parents1中\n",
    "        while(region2 not in parents1):\n",
    "            region2 = parents[region2]\n",
    "        return region2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        fa=collections.Counter()\n",
    "        path=set()\n",
    "        for a in regions:\n",
    "            n=len(a)\n",
    "            for i in range(1,n):\n",
    "                fa[a[i]]=a[0]\n",
    "       # print(fa)\n",
    "        while region1 in fa:\n",
    "            path.add(region1)\n",
    "            region1=fa[region1]\n",
    "        path.add(region1)\n",
    "        if region2 in path:\n",
    "            return region2\n",
    "        while region2  not in path:\n",
    "            region2=fa[region2]\n",
    "            #if region2 in path:\n",
    "             #   return region2\n",
    "           # print(region2)\n",
    "        return region2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Travel up. Time O(n) Space O(n)\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        parent = {}\n",
    "        for region in regions:\n",
    "            for i in range(1, len(region)):\n",
    "                parent[region[i]] = region[0]\n",
    "        # parents1 save all nodes in the path from region1 to root\n",
    "        parents1 = set()\n",
    "        cur = region1\n",
    "        while cur in parent.keys():\n",
    "            parents1.add(cur)\n",
    "            cur = parent[cur]\n",
    "        # go from region2 to root\n",
    "        cur = region2\n",
    "        while cur in parent.keys():\n",
    "            if cur in parents1:\n",
    "                return cur\n",
    "            cur = parent[cur]\n",
    "        return cur  # LCA must be the root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        g=collections.defaultdict(list)\n",
    "        for i in regions:\n",
    "            for x in i[1:]:\n",
    "                g[x].append(i[0])\n",
    "        #print(g)\n",
    "        \n",
    "        x=region1\n",
    "        ls=[x]\n",
    "        while x in g:\n",
    "            ls.append(g[x][0])\n",
    "            x=g[x][0]\n",
    "        #print(ls)\n",
    "        y=region2\n",
    "        while y not in ls:\n",
    "            y=g[y][0]\n",
    "        return y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        # 多叉树的最近公共祖先\n",
    "        # 用哈希表储存每一个region的父区域\n",
    "        parents = dict()\n",
    "        for region in regions:\n",
    "            for i in range(1, len(region)):\n",
    "                parents[region[i]] = region[0]\n",
    "        # 先找到regions1自底向上的全部父区域，存在parents1哈希集合中\n",
    "        parents1 = {region1}\n",
    "        while(region1 in parents):\n",
    "            parents1.add(parents[region1])\n",
    "            region1 = parents[region1]\n",
    "        # 寻找regions2自底向上的每一个父区域，判断其是否位于parents1中\n",
    "        while(region2 not in parents1):\n",
    "            region2 = parents[region2]\n",
    "        return region2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        g=collections.defaultdict(list)\n",
    "        for i in regions:\n",
    "            for x in i[1:]:\n",
    "                g[x].append(i[0])\n",
    "        #print(g)\n",
    "        \n",
    "        x=region1\n",
    "        ls=[x]\n",
    "        while x in g:\n",
    "            ls.append(g[x][0])\n",
    "            x=g[x][0]\n",
    "        #print(ls)\n",
    "        y=region2\n",
    "        while y not in ls:\n",
    "            y=g[y][0]\n",
    "        return y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        # 多叉树的最近公共祖先\n",
    "        # 用哈希表储存每一个region的父区域\n",
    "        parents = dict()\n",
    "        for region in regions:\n",
    "            for i in range(1, len(region)):\n",
    "                parents[region[i]] = region[0]\n",
    "        # 先找到regions1自底向上的全部父区域，存在parents1哈希集合中\n",
    "        parents1 = {region1}\n",
    "        while(region1 in parents):\n",
    "            parents1.add(parents[region1])\n",
    "            region1 = parents[region1]\n",
    "        # 寻找regions2自底向上的每一个父区域，判断其是否位于parents1中\n",
    "        while(region2 not in parents1):\n",
    "            region2 = parents[region2]\n",
    "        return region2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "\n",
    "        parents = {}\n",
    "        for region in regions:\n",
    "            for i in range(1, len(region)):\n",
    "                parents[region[i]] = region[0]\n",
    "        \n",
    "        region1_parents = set()\n",
    "        p = region1\n",
    "        while p in parents:\n",
    "            region1_parents.add(p)\n",
    "            p = parents[p]\n",
    "\n",
    "        q = region2\n",
    "        while q in parents and q not in region1_parents:\n",
    "            q = parents[q]\n",
    "        \n",
    "        return q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        fa=collections.Counter()\n",
    "        path=set()\n",
    "        for a in regions:\n",
    "            n=len(a)\n",
    "            for i in range(1,n):\n",
    "                fa[a[i]]=a[0]\n",
    "        print(fa)\n",
    "        while region1 in fa:\n",
    "            path.add(region1)\n",
    "            region1=fa[region1]\n",
    "     \n",
    "        while region2  in fa:\n",
    "            if region2 in path:\n",
    "                return region2\n",
    "            region2=fa[region2]\n",
    "            if region2 in path:\n",
    "                return region2\n",
    "           # print(region2)\n",
    "        return region2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        fa=collections.Counter()\n",
    "        path=set()\n",
    "        for a in regions:\n",
    "            n=len(a)\n",
    "            for i in range(1,n):\n",
    "                fa[a[i]]=a[0]\n",
    "        print(fa)\n",
    "        while region1 in fa:\n",
    "            path.add(region1)\n",
    "            region1=fa[region1]\n",
    "        if region2 in path:\n",
    "                return region2\n",
    "        while region2  in fa:\n",
    "            region2=fa[region2]\n",
    "            if region2 in path:\n",
    "                return region2\n",
    "           # print(region2)\n",
    "        return region2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "        self.father=None\n",
    "class Solution:\n",
    "    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:\n",
    "        dic={}\n",
    "        def dic_method(n):\n",
    "            nonlocal dic\n",
    "            if dic.get(n)==None:\n",
    "                dic[n]=Node()\n",
    "                dic[n].val=n\n",
    "        \n",
    "        for r in regions:\n",
    "            father=r[0]\n",
    "            dic_method(father)\n",
    "            for idt in range(1,len(r)):\n",
    "                child=r[idt]\n",
    "                dic_method(child)\n",
    "                if dic[child] not in dic[father].children:\n",
    "                    dic[father].children.append(dic[child])\n",
    "                    dic[child].father=dic[father]\n",
    " \n",
    "\n",
    "        r1_line=[]\n",
    "        def method1(node):\n",
    "            nonlocal r1_line\n",
    "\n",
    "            if node!=None:\n",
    "                r1_line.append(node.val)\n",
    "                node=method1(node.father)\n",
    "        method1(dic[region1])\n",
    "        r2_line=[]\n",
    "        def method2(node):\n",
    "            nonlocal r2_line\n",
    "            if node!=None:\n",
    "                r2_line.append(node.val)\n",
    "                node=method2(node.father)\n",
    "        method2(dic[region2])\n",
    "\n",
    "        for i in r1_line:\n",
    "            if i in r2_line:\n",
    "                return i\n",
    "        \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
